#include <set>
#include <vector>
#include <iostream>

using namespace std;

int firstDuplicate(vector<int> &array) {
  set<int> coll;
  // coll
  // {}

  for (int n : array) {
    // 问 coll: 你里面有数字 n 么？
    // 有：说明我们找到了重复的数字，返回 n
    // 没有：我们就把 n 添加到 coll
    // find(n)
    //  - 找到了：set<int>::iterator
    //  - 没找到：coll.end()
    if (coll.find(n) != coll.end()) {
      // 找到了
      return n;
    }
    else {
      coll.insert(n);
    }
  }

  return -1;
}

int main(int argc, char const *argv[])
{
  vector<int> v {1, 3, 5, 7, 8, 3};
  cout<<firstDuplicate(v)<<endl;
  return 0;
}
